home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / editors / emacs / xemacs / xemacs-1.004 / xemacs-1 / xemacs-19.13 / lisp / oobr / tree-x / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-29  |  17.6 KB  |  726 lines
  1. /* ----------------------------------------------------------------------------
  2.  * File    : tree.c
  3.  * Purpose : dynamic tree program based on Sven Moen's algorithm
  4.  * ----------------------------------------------------------------------------
  5.  */
  6.  
  7. #include "defs.h"
  8. #include "tree.h"
  9. #include "dbl.h"
  10. #include "intf.h"
  11. #include <string.h>
  12.  
  13. /* ------------------------------------------------------------------------- */
  14. /*                Global Variables                             */
  15. /* ------------------------------------------------------------------------- */
  16.  
  17. int NumLines = 0;
  18. int NumNodes = 0;
  19.  
  20.  
  21. /* ----------------------------------------------------------------------------
  22.  * 
  23.  *   MakeLine() allocates the memory required for a Polyline and 
  24.  *   initializes the fields of a Polyline to the arguments. The
  25.  *   newly-allocated Polyline is returned by the function.
  26.  * 
  27.  * ----------------------------------------------------------------------------
  28.  */
  29.  
  30. Polyline*
  31. MakeLine(dx, dy, link)
  32.    short dx;
  33.    short dy;
  34.    Polyline *link;
  35. {
  36.    Polyline *new;
  37.  
  38.    new = (Polyline *) malloc(sizeof(Polyline));
  39.    NASSERT(new, "could not allocate memory for polyline");
  40.    NumLines++;
  41.  
  42.    new->dx = dx;
  43.    new->dy = dy;
  44.    new->link = link;
  45.  
  46.    return (new);
  47. }
  48.  
  49. /* ----------------------------------------------------------------------------
  50.  * 
  51.  *   MakeNode() allocates the memory required for a tree node, and
  52.  *   zeros out all the fields in the Node. It returns a pointer to the
  53.  *   tree node upon success, and NULL upon failure.
  54.  * 
  55.  * ----------------------------------------------------------------------------
  56.  */
  57.  
  58. Tree*
  59. MakeNode()
  60. {
  61.    Tree *node;
  62.    
  63.    node = (Tree *) malloc(sizeof(Tree));
  64.    NASSERT(node, "could not allocate memory for node");
  65.    NumNodes++;
  66.  
  67.    if (node == NULL)
  68.       return (NULL);
  69.    else {
  70. #ifdef SYSV
  71.       memset((char *) node, 0, sizeof(Tree));
  72. #else
  73.       bzero((char *) node, sizeof(Tree));
  74. #endif
  75.       return (node);
  76.    }
  77. }
  78.  
  79. /* ----------------------------------------------------------------------------
  80.  * 
  81.  *   MakeBridge()
  82.  * 
  83.  * ----------------------------------------------------------------------------
  84.  */
  85.  
  86. Polyline*
  87. MakeBridge(line1, x1, y1, line2, x2, y2)
  88.    Polyline *line1, *line2;
  89.    int x1, x2, y1, y2;
  90. {
  91.    int dx, dy, s;
  92.    Polyline *r;
  93.  
  94.    dx = x2 + line2->dx - x1;
  95.    if (line2->dx == 0)
  96.       dy = line2->dy;
  97.    else {
  98.       s = dx * line2->dy;
  99.       dy = s / line2->dx;
  100.    }
  101.    r = MakeLine(dx, dy, line2->link);
  102.    line1->link = MakeLine(0, y2 + line2->dy - dy - y1, r);
  103.  
  104.    return (r);
  105. }
  106.  
  107. /* ----------------------------------------------------------------------------
  108.  * 
  109.  *   Offset() computes the necessary offset that prevents two line segments
  110.  *   from intersecting each other. This is the "heart" of the merge step
  111.  *   that computes how two subtree contours should be separated. 
  112.  * 
  113.  *   The code is taken directly from Sven Moen's paper, with changes in
  114.  *   some variable names to give more meaning: 
  115.  *   
  116.  *   - px,py indicate the x- and y-coordinates of the point on the longer
  117.  *     segment if the previous Offset() call had two unequal segments
  118.  * 
  119.  *   - lx,ly indicate the dx and dy values of the "lower" line segment
  120.  * 
  121.  *   - ux,uy indicate the dx and dy values of the "upper" line segment
  122.  * 
  123.  * ----------------------------------------------------------------------------
  124.  */
  125.  
  126. int
  127. Offset(px, py, lx, ly, ux, uy)
  128.    int px, py, lx, ly, ux, uy;
  129. {
  130.    int d, s, t;
  131.  
  132.    if (ux <= px || px+lx <= 0)
  133.       return 0;
  134.  
  135.    t = ux*ly - lx*uy;
  136.  
  137.    if (t > 0) {
  138.       if (px < 0) {
  139.      s = px*ly;
  140.      d = s/lx - py;
  141.       }
  142.       else if (px > 0) {
  143.      s = px*uy;
  144.      d = s/ux - py;
  145.       }
  146.       else {
  147.      d = -py;
  148.       }
  149.    }
  150.    else {
  151.       if (ux < px+lx) {
  152.      s = (ux-px) * ly;
  153.      d = uy - (py + s/lx);
  154.       }
  155.       else if (ux > px+lx) {
  156.      s = (lx+px) * uy;
  157.      d = s/ux - (py+ly);
  158.       }
  159.       else {
  160.      d = uy - (py+ly);
  161.       }
  162.    }
  163.  
  164.    return MAX(0, d);
  165. }
  166.  
  167. /* ----------------------------------------------------------------------------
  168.  * 
  169.  *   Merge()
  170.  * 
  171.  * ----------------------------------------------------------------------------
  172.  */
  173.  
  174. int
  175. Merge(c1, c2)
  176.    Polygon *c1, *c2;
  177. {
  178.    int x, y, total, d;
  179.    Polyline *lower, *upper, *bridge;
  180.  
  181.    x = y = total = 0;
  182.  
  183.    /*  compare lower part of upper child's contour 
  184.     *  with upper part of lower child's contour
  185.     */
  186.    upper = c1->lower.head;
  187.    lower = c2->upper.head;
  188.  
  189.    while (lower && upper) {
  190.       d = Offset(x, y, lower->dx, lower->dy, upper->dx, upper->dy);
  191.       y += d;
  192.       total += d;
  193.  
  194.       if (x + lower->dx <= upper->dx) {
  195.      x += lower->dx;
  196.      y += lower->dy;
  197.      lower = lower->link;
  198.       }
  199.       else {
  200.      x -= upper->dx;
  201.      y -= upper->dy;
  202.      upper = upper->link;
  203.       }
  204.    }
  205.      
  206.    if (lower) {
  207.       bridge = MakeBridge(c1->upper.tail, 0, 0, lower, x, y);
  208.       c1->upper.tail = (bridge->link) ? c2->upper.tail : bridge;
  209.       c1->lower.tail = c2->lower.tail;
  210.    }
  211.    else {
  212.       bridge = MakeBridge(c2->lower.tail, x, y, upper, 0, 0);
  213.       if (!bridge->link) 
  214.      c1->lower.tail = bridge;
  215.    }
  216.    c1->lower.head = c2->lower.head;
  217.  
  218.    return (total);
  219. }
  220.  
  221. /* ----------------------------------------------------------------------------
  222.  * 
  223.  *   DetachParent() reverses the effects of AttachParent by removing
  224.  *   the four line segments that connect the subtree contour to the
  225.  *   node specified by 'tree'. 
  226.  * 
  227.  * ----------------------------------------------------------------------------
  228.  */
  229.  
  230. void
  231. DetachParent(tree)
  232.    Tree *tree;
  233. {
  234.    free(tree->contour.upper.head->link);
  235.    free(tree->contour.upper.head);
  236.    tree->contour.upper.head = NULL;
  237.    tree->contour.upper.tail = NULL;
  238.  
  239.    free(tree->contour.lower.head->link);
  240.    free(tree->contour.lower.head);
  241.    tree->contour.lower.head = NULL;
  242.    tree->contour.lower.tail = NULL;
  243.  
  244.    NumLines -= 4;
  245. }
  246.  
  247. /* ----------------------------------------------------------------------------
  248.  * 
  249.  *   AttachParent() 
  250.  *   This function also establishes the position of the first child
  251.  *   The code follows Sven Moen's version, with slight modification to
  252.  *   support varying borders at different levels.
  253.  * 
  254.  * ----------------------------------------------------------------------------
  255.  */
  256.  
  257. void
  258. AttachParent(tree, h)
  259.    Tree *tree;
  260.    int h;
  261. {
  262.    int x, y1, y2;
  263.  
  264.    if (TreeAlignNodes)
  265.       x = tree->border + (TreeParentDistance * 2) +
  266.      (TreeParentDistance - tree->width);
  267.    else
  268.       x = tree->border + TreeParentDistance;
  269.    y2 = (h - tree->height)/2 - tree->border;
  270.    y1 = y2 + tree->height + (2 * tree->border) - h; 
  271.    tree->child->offset.x = x + tree->width;
  272.    tree->child->offset.y = y1;
  273.    tree->contour.upper.head = MakeLine(tree->width, 0,
  274.                        MakeLine(x, y1,
  275.                         tree->contour.upper.head));
  276.    tree->contour.lower.head = MakeLine(tree->width, 0,
  277.                        MakeLine(x, y2,
  278.                         tree->contour.lower.head));
  279. }
  280.  
  281. /* ----------------------------------------------------------------------------
  282.  * 
  283.  *   Split()
  284.  *   The tree passed to Split() must have at least 1 child, because
  285.  *   it doesn't make sense to split a leaf (there are no bridges)
  286.  * 
  287.  * ----------------------------------------------------------------------------
  288.  */
  289.  
  290. void
  291. Split(tree)
  292.    Tree *tree;
  293. {
  294.    Tree *child;
  295.    Polyline *link;
  296.  
  297.    FOREACH_CHILD(child, tree) {
  298.       if (link = child->contour.upper.tail->link) {
  299.      free(link->link);
  300.      free(link);
  301.      child->contour.upper.tail->link = NULL;
  302.      NumLines -= 2;
  303.       }
  304.       if (link = child->contour.lower.tail->link) {
  305.      free(link->link);
  306.      free(link);
  307.      NumLines -= 2;
  308.      child->contour.lower.tail->link = NULL;
  309.       }
  310.    }
  311. }
  312.  
  313. /* ----------------------------------------------------------------------------
  314.  * 
  315.  *   Join() merges all subtree contours of the given tree and returns the
  316.  *   height of the entire tree contour. 
  317.  * 
  318.  * ----------------------------------------------------------------------------
  319.  */
  320.  
  321. int
  322. Join(tree)
  323.    Tree *tree;
  324. {
  325.    Tree *child;
  326.    int d, h, sum;
  327.  
  328.    /*   to start, set the parent's contour and height
  329.     *   to contour and height of first child 
  330.     */
  331.    child = tree->child;
  332.    tree->contour = child->contour;
  333.    sum = h = child->height + (2 * child->border);
  334.  
  335.    /* extend contour to include contours of all children of parent */
  336.    for (child = child->sibling ; child ; child = child->sibling) {
  337.       d = Merge(&tree->contour, &child->contour);
  338.       child->offset.y = d + h;
  339.       child->offset.x = 0;
  340.       h = child->height + (2 * child->border);
  341.       /* keep cumulative heights of subtree contours */
  342.       sum += d + h;
  343.    }
  344.    return sum;
  345. }
  346.  
  347. /* ----------------------------------------------------------------------------
  348.  * 
  349.  *   RuboutLeaf() accepts a single node (leaf) and removes its contour.
  350.  *   The memory associated with the contour is deallocated. 
  351.  * 
  352.  * ----------------------------------------------------------------------------
  353.  */
  354.  
  355. void
  356. RuboutLeaf(tree)
  357.    Tree *tree;
  358. {
  359.    free(tree->contour.upper.head);
  360.    free(tree->contour.lower.tail);
  361.    free(tree->contour.lower.head);
  362.    tree->contour.upper.head = NULL;   
  363.    tree->contour.upper.tail = NULL;   
  364.    tree->contour.lower.head = NULL;   
  365.    tree->contour.lower.tail = NULL;   
  366.    NumLines -= 3;
  367. }
  368.  
  369. /* ----------------------------------------------------------------------------
  370.  * 
  371.  *   LayoutLeaf() accepts a single node (leaf) and forms its contour. This
  372.  *   function assumes that the width, height, and border fields of the 
  373.  *   node have been assigned meaningful values.
  374.  * 
  375.  * ----------------------------------------------------------------------------
  376.  */
  377.  
  378. void
  379. LayoutLeaf(tree)
  380.    Tree *tree;
  381. {
  382.    tree->node_height = 0;
  383.    tree->border = TreeBorderSize;
  384.  
  385.    tree->contour.upper.tail = MakeLine(tree->width + 2 * tree->border, 0,
  386.                        NULL);
  387.    tree->contour.upper.head = tree->contour.upper.tail;
  388.    
  389.    tree->contour.lower.tail = MakeLine(0, -tree->height - 2 * tree->border,
  390.                        NULL);
  391.    tree->contour.lower.head = MakeLine(tree->width + 2 * tree->border, 0,
  392.                        tree->contour.lower.tail);
  393.  
  394. }
  395.  
  396. /* ----------------------------------------------------------------------------
  397.  * 
  398.  *   LayoutTree() traverses the given tree (in depth-first order), and forms
  399.  *   subtree or leaf contours at each node as needed. Each node's contour is
  400.  *   stored in its "contour" field. Elision is also supported by generating
  401.  *   the contour for both the expanded and collapsed node. This routine
  402.  *   also computes the tree height of each node in the tree, so that variable
  403.  *   density layout can be demonstrated.
  404.  * 
  405.  * ----------------------------------------------------------------------------
  406.  */
  407.  
  408. void
  409. LayoutTree(tree)
  410.    Tree *tree;
  411. {
  412.    Tree *child;
  413.    int   height = 0;
  414.  
  415.    FOREACH_CHILD(child, tree) {
  416.       LayoutTree(child);
  417.  
  418.       if (child->elision) {    /* support elision */
  419.      child->old_contour = child->contour;
  420.      LayoutLeaf(child);
  421.       }
  422.  
  423.    }
  424.  
  425.    if (tree->child) {
  426.  
  427.       FOREACH_CHILD(child, tree) 
  428.      height = MAX(child->node_height, height);
  429.       tree->node_height = height + 1;
  430.  
  431.       if (TreeLayoutDensity == Fixed)
  432.      tree->border = TreeBorderSize;
  433.       else
  434.      tree->border =
  435.         (int) (TreeBorderSize * (tree->node_height * DENSITY_FACTOR));
  436.  
  437.       AttachParent(tree, Join(tree));
  438.    }
  439.    else
  440.       LayoutLeaf(tree);
  441. }
  442.  
  443. /* ------------------------------------------------------------------------- */
  444.  
  445. void
  446. Unzip(tree)
  447.    Tree *tree;
  448. {
  449.    Tree *child;
  450.  
  451. #ifdef INTF
  452.    if (TreeShowSteps) {
  453.       HiliteNode(tree, New);
  454.       tree->on_path = TRUE;
  455.       StatusMsg("Unzip: follow parent links up to root");
  456.       Pause();
  457.    }
  458. #endif   
  459.  
  460.    if (tree->parent)
  461.       Unzip(tree->parent);
  462.  
  463.    if (tree->child) {
  464.  
  465. #ifdef INTF
  466.       /*   draw entire contour; do it only for root, because the last
  467.        *   frame drawn in this function will have already drawn the  
  468.        *   contour for the most recently split subtree.              
  469.        */
  470.       if (TreeShowSteps) {
  471.      if (tree->parent == NULL) {
  472.         BeginFrame();
  473.           DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
  474.           DrawTree(TheTree, New);
  475.         EndFrame();
  476.         StatusMsg("Unzip: disassemble entire contour");
  477.         Pause();
  478.      }
  479.       }
  480. #endif
  481.  
  482. #ifdef INTF
  483.       /* draw contour as it would appear after DetachParent() */
  484.       if (TreeShowSteps) {
  485.      BeginFrame();
  486.        DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE,
  487.                FALSE, FALSE, FALSE);
  488.        DrawTree(TheTree, New);
  489.      EndFrame();
  490.      StatusMsg("Unzip: detach parent");
  491.      Pause();
  492.       }
  493. #endif
  494.  
  495.       DetachParent(tree);
  496.       Split(tree);
  497.  
  498. #ifdef INTF
  499.       if (TreeShowSteps) {
  500.      BeginFrame();
  501.            /* mark other subtree contours as split, and */
  502.        /* draw only the contour on path in full     */
  503.        FOREACH_CHILD(child, tree) {
  504.           if (!child->on_path) 
  505.          child->split = TRUE;
  506.           else
  507.          DrawTreeContour(child, New, CONTOUR_COLOR,
  508.                  FALSE, FALSE, FALSE);
  509.        }
  510.        DrawTree(TheTree, New);
  511.      EndFrame();
  512.      StatusMsg("Unzip: split tree");
  513.      Pause();
  514.       }
  515. #endif
  516.  
  517.    }
  518.    else
  519.       RuboutLeaf(tree);        /* leaf node */
  520. }
  521.  
  522. /* ------------------------------------------------------------------------- */
  523.  
  524. void
  525. Zip(tree)
  526.    Tree *tree;
  527. {
  528.    if (tree->child)
  529.       AttachParent(tree, Join(tree));
  530.    else
  531.       LayoutLeaf(tree);
  532.  
  533.    if (tree->parent)
  534.       Zip(tree->parent);
  535. }
  536.  
  537. /* ----------------------------------------------------------------------------
  538.  * 
  539.  *   Insert() adds the specified child to parent, just after the specified
  540.  *   sibling. If 'sibling' is Null, the child is added as the first child.
  541.  * 
  542.  * ----------------------------------------------------------------------------
  543.  */
  544.  
  545. void
  546. Insert(parent, child, sibling)
  547.    Tree *parent, *child, *sibling;
  548. {
  549.    Unzip(parent);
  550.    child->parent = parent;
  551.    if (sibling) {
  552.       child->sibling = sibling->sibling;
  553.       sibling->sibling = child;
  554.    }
  555.    else {
  556.       child->sibling = parent->child;
  557.       parent->child = child;
  558.    }
  559.    Zip(parent);
  560. }
  561.  
  562.  
  563.  
  564.  
  565. /* ----------------------------------------------------------------------------
  566.  * 
  567.  *   Delete() traverses the specified tree and frees all storage
  568.  *   allocated to the subtree, including contours and bridges.
  569.  *   If the tree had a preceding sibling, the preceding sibling is
  570.  *   modified to point to the tree's succeeding sibling, if any.
  571.  * 
  572.  * ----------------------------------------------------------------------------
  573.  */
  574.  
  575. Delete(tree)
  576.    Tree *tree;
  577. {
  578.    Tree *sibling = NULL;
  579.    Tree *parent, *child;
  580.  
  581.    /* find sibling */
  582.    parent = tree->parent;
  583.    if (parent) {
  584.       FOREACH_CHILD(child, parent)
  585.      if (child->sibling == tree) {
  586.         sibling = child;
  587.         break;
  588.      }
  589.    }
  590.    if (sibling)
  591.       sibling->sibling = tree->sibling;
  592.    else if (parent)
  593.       parent->child = tree->sibling;
  594.    
  595.    DeleteTree(tree, FALSE);
  596. }
  597.  
  598.  
  599. /* ----------------------------------------------------------------------------
  600.  * 
  601.  *   DeleteTree() is the recursive function that supports Delete(). 
  602.  *   If 'contour' is True, then only the contours are recursively deleted.
  603.  *   This flag should be True when you are regenerating a tree's layout
  604.  *   and still want to preserve the nodes. Since contours would be deleted
  605.  *   only due to a change in sibling or level distance, each node's border
  606.  *   value is updated with the current value of TreeBorderSize;
  607.  * 
  608.  * ----------------------------------------------------------------------------
  609.  */
  610.  
  611. DeleteTree(tree, contour)
  612.    Tree *tree;
  613.    int   contour;
  614. {
  615.    Tree *child;
  616.  
  617.    if (tree->elision) {
  618.       RuboutLeaf(tree);
  619.       tree->contour = tree->old_contour;
  620.       tree->old_contour.upper.head = NULL;    /* flag to note 'NULL' contour */
  621.    }
  622.  
  623.    if (!IS_LEAF(tree)) {
  624.       DetachParent(tree);
  625.       Split(tree);
  626.  
  627.       FOREACH_CHILD(child,tree)
  628.      DeleteTree(child, contour);
  629.    }
  630.    else
  631.       RuboutLeaf(tree);
  632.  
  633.    if (contour) 
  634.       tree->border = TreeBorderSize;
  635.    else {
  636.       free(tree->label.text);
  637.       free(tree);
  638.       NumNodes--;
  639.    }
  640. }
  641.  
  642.  
  643. /* ----------------------------------------------------------------------------
  644.  * 
  645.  *   ComputeTreeSize() 
  646.  *   This function should be called after tree layout.
  647.  * 
  648.  * ----------------------------------------------------------------------------
  649.  */
  650.  
  651. void
  652. ComputeTreeSize(tree, width, height, x_offset, y_offset)
  653.    Tree *tree;
  654.    int *width, *height;
  655.    int *x_offset, *y_offset;
  656. {
  657.    Polyline *contour, *tail;
  658.    int upper_min_y = 0, lower_max_y = 0;
  659.    int upper_abs_y = 0, lower_abs_y = 0;
  660.    int x = 0;
  661.  
  662.    /* do upper contour */
  663.    contour = tree->contour.upper.head;
  664.    tail    = tree->contour.upper.tail;
  665.    while (contour) {
  666.       if ((contour->dy + upper_abs_y) < upper_min_y) 
  667.      upper_min_y = contour->dy + upper_abs_y;
  668.       upper_abs_y += contour->dy;
  669.       if (contour == tail)
  670.      contour = NULL;
  671.       else
  672.      contour = contour->link;
  673.    }
  674.  
  675.    /* do lower contour */
  676.    contour = tree->contour.lower.head;
  677.    tail    = tree->contour.lower.tail;
  678.    while (contour) {
  679.       if ((contour->dy + lower_abs_y) > lower_max_y)
  680.      lower_max_y = contour->dy + lower_abs_y;
  681.       lower_abs_y += contour->dy;
  682.       x += contour->dx;
  683.       if (contour == tail)
  684.      contour = NULL;
  685.       else
  686.      contour = contour->link;
  687.    }
  688.  
  689.    *width = x + 1;
  690.    *height = lower_max_y - upper_min_y +
  691.              (tree->height + (2 * tree->border)) + 1;
  692.    if (x_offset)
  693.       *x_offset = tree->border;
  694.    if (y_offset)
  695.       *y_offset = - upper_min_y + tree->border;
  696. }
  697.  
  698. /* ----------------------------------------------------------------------------
  699.  * 
  700.  *   PetrifyTree()
  701.  * 
  702.  * ----------------------------------------------------------------------------
  703.  */
  704.  
  705. void
  706. PetrifyTree(tree, x, y)
  707.    Tree *tree;
  708.    int x, y;
  709. {
  710.    int width, height;
  711.    int x_offset, y_offset;
  712.    
  713.    tree->old_pos = tree->pos;    /* used by AnimateTree */
  714.  
  715.    /* fix position of each node */
  716.    tree->pos.x = x + tree->offset.x;
  717.    tree->pos.y = y + tree->offset.y;
  718.    
  719.    if (tree->child) {
  720.       PetrifyTree(tree->child, tree->pos.x, tree->pos.y);
  721.       ComputeSubTreeExtent(tree); /* for benefit of interface picking */
  722.    }
  723.    if (tree->sibling)
  724.       PetrifyTree(tree->sibling, tree->pos.x, tree->pos.y);
  725. }
  726.